package cn.hdu.liang.ch2;

import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
        int[] a = {1, 6, 2, 9, 8, 3, 5, 4, 7, 0};
        //insertSort(a); //传统插入排序
        recurInsertSort(a, a.length);//递归插入排序
        System.out.println(Arrays.toString(a));
    }

    public static void insertSort(int[] a) {
        for(int i = 1; i < a.length; i++) {
            if(a[i - 1] > a[i]) {
                int temp = a[i];
                int j = i;
                while(j > 0 && a[j - 1] > temp) {
                    a[j] = a[j - 1];
                    j--;
                }
                a[j] = temp;
            }
        }
    }

    public static void recurInsertSort(int[] a, int length) {

        if(length == 1) {
            return;
        }
        recurInsertSort(a, --length);
        insert(a, length);

    }

    public static void insert(int[] a, int p) {
        int temp = a[p];
        int j = p;
        while(j > 0 && a[j - 1] > temp) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = temp;
    }


}
